package leetcode100

// TODO 变异的二分法 【-】 搜索旋转排序数组
// TODO https://leetcode.cn/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-er-fen-92jot/
// TODO 由于要求时间复杂度 logn, 所以自然联想到 二分法

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (right-left)/2 + left
		if nums[mid] == target {
			return mid
		}
		// 因为 left 是旋转点, 所以都和 left 进行对比
		if nums[mid] >= nums[left] {
			// mid 在左
			if nums[mid] > target && target >= nums[left] { // target 在 A 段
				right = mid - 1
			} else {
				// target 在 B 和 C 段时的操作一样
				left = mid + 1
			}
		} else {
			// mid 在右
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}
